package com.fw.structure.tree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.ToString;

/**
 * 二叉树的应用说明
 */
public class BinaryTreeDemo {
    public static int num = 0 ;


    public static void main(String[] args) {
        // 添加节点 root 节点
        BinaryNode binaryNode1 = new BinaryNode("小红",1);
        BinaryNode binaryNode2 = new BinaryNode("小蓝",2);
        BinaryNode binaryNode3 = new BinaryNode("小黑",3);
        BinaryNode binaryNode4 = new BinaryNode("小白",4);
        BinaryNode binaryNode5 = new BinaryNode("小绿",5);
        BinaryNode binaryNode6 = new BinaryNode("小灰",6);

        binaryNode1.setLeftNode(binaryNode2);
        binaryNode1.setRightNode(binaryNode3);

        binaryNode3.setLeftNode(binaryNode5);
        binaryNode3.setRightNode(binaryNode6);

        binaryNode5.setRightNode(binaryNode4);

        BinaryTree binaryTree = new BinaryTree(binaryNode1);
       // binaryTree.afterFor();
        //BinaryNode binaryNode = binaryTree.preambleSearch(5); // 前序查找 编号为 5 的一共查了 4 次
        //System.out.println(num);

                                // 中序查找 编号 为 5 的一共比对了 3次
        //BinaryNode binaryNode = binaryTree.middleSearch(5);
      //  System.out.println(num);

        // 后序查找 编号 为 5 的一共比对了 3次
        //BinaryNode binaryNode = binaryTree.afterSearch(5);

       // System.out.println(num);
       // if (binaryNode != null){
       //     System.out.println(binaryNode);
      //  }else{
      //      System.out.println("未找到!");
       // }
        binaryTree.delNode(3);
        binaryTree.preambleFor();
    }




}

/**
 * 创建二叉树
 */
@AllArgsConstructor
class  BinaryTree{
    private BinaryNode binaryNode;

    // 前序遍历
    public void preambleFor(){
        binaryNode.preambleFor();
    }

    // 中序遍历
    public void middleFor(){
        binaryNode.middleFor();
    }

    // 后序遍历
    public void afterFor(){
        binaryNode.afterFor();
    }

    // 前序查找
    public BinaryNode preambleSearch(int no){
        return binaryNode.preambleSearch(no);
    }

    // 中序查找
    public BinaryNode middleSearch(int no){
        return binaryNode.middleSearch(no);
    }

    // 后序查找
    public BinaryNode afterSearch(int no){
        return binaryNode.afterSearch(no);
    }

   // 删除指定节点
    public void delNode(int noNumber){
        if (binaryNode != null){
            if ( binaryNode.getNoNumber() == noNumber){
                this.binaryNode = null;
                return;
            }
            binaryNode.delNode(noNumber);
        }else
        throw new RuntimeException("is not null binaryNode");

    }

}


/**
 * 二叉树节点
 * 分为 左节点 右节点等
 */
@Data
@ToString
class BinaryNode{
    // 节点姓名
    private String nodeName;
    // 节点 编号
    private int noNumber;

    public BinaryNode(String nodeName, int noNumber) {
        this.nodeName = nodeName;
        this.noNumber = noNumber;
    }

    // 分为 左节点
    @ToString.Exclude
    private BinaryNode leftNode;
    // 以及 右节点
    @ToString.Exclude
    private BinaryNode rightNode;





    /**
     * 前序遍历规则
     * 1. 输出当前节点
     * 2. 如果当前左节点不为空继续前序遍历
     * 3. 如果当前右节点不为空继续前序遍历
     */
    public void preambleFor(){
        // 输出当前节点
        System.out.println(this.toString());

        // 如果左节点不为空继续前序遍历
        if (this.leftNode != null)
            this.leftNode.preambleFor();
        // 如果当前右节点不为空继续前序遍历
        if (this.rightNode != null)
            this.rightNode.preambleFor();
    }


    /**
     * 中序遍历规则
     * 1. 如果当前左节点不为空则继续中序遍历
     * 2. 输出当前节点
     * 3. 如果当前右节点不为空则继续中序遍历
     */
    public void middleFor(){
        if (this.leftNode != null)
            this.leftNode.middleFor();

        System.out.println(this.toString());

        if (this.rightNode != null)
            this.rightNode.middleFor();
    }

    /**
     * 后序遍历规则
     * 1. 如果当前左节点不为空则继续中序遍历
     * 2. 如果当前右节点不为空则继续中序遍历
     * 3. 输出当前节点
     */
    public void afterFor(){
        if (this.leftNode != null)
            this.leftNode.afterFor();

        if (this.rightNode != null)
            this.rightNode.afterFor();

        System.out.println(this.toString());
    }

    /**
     * 前序查找规则
     * 1. 比较当前节点，如果是的话就返回
     * 2. 如果当前节点不是的话，继续左节点前序查找。
     * 3. 如果左节点没找到的话，就右节点前序查找
     */
    public BinaryNode preambleSearch(int no){
        //1. 比较当前节点，如果是的话就返回
        ++BinaryTreeDemo.num;
        if (no == this.noNumber){
            return this;
        }
        //2. 如果当前节点不是的话，继续左节点前序查找。
        BinaryNode binaryNode = null;
        if (this.leftNode != null && (binaryNode = this.leftNode.preambleSearch(no)) != null)
            return binaryNode;
        //3. 如果左节点没找到的话，就右节点前序查找
        if (this.rightNode != null &&  (binaryNode = this.rightNode.preambleSearch(no)) != null)
            return binaryNode;
        // 最后返回
        return binaryNode;
    }

    /**
     * 中序 查找规则
     * 1. 左中序查找,
     * 2. 和当前节点比较,如果是的话就 返回.
     * 3. 右中序查找.
     */
    public BinaryNode middleSearch(int no){
        BinaryNode binaryNode = null;
        //1. 左中序查找,
        if (this.leftNode != null &&  (binaryNode = this.leftNode.middleSearch(no)) != null)
            return binaryNode;
        //2. 和当前节点比较,如果是的话就 返回.
        ++BinaryTreeDemo.num;
        if (this.noNumber == no){
            return this;
        }
       // 3. 右中序查找.
        if (this.rightNode != null &&  (binaryNode = this.rightNode.middleSearch(no)) != null)
            return binaryNode;

        return binaryNode;
    }

    /**
     * 后序查找方式
     * 1. 进行左后序查询.
     * 2. 进行右后序查询.
     * 3. 与当前节点进行比较
     */
    public BinaryNode afterSearch(int no){
        BinaryNode binaryNode = null;
       // 1. 进行左后序查询.
        if (this.leftNode != null &&  (binaryNode = this.leftNode.afterSearch(no)) != null)
            return binaryNode;

        // 2. 进行右后序查询.
        if (this.rightNode != null &&  (binaryNode = this.rightNode.afterSearch(no)) != null)
            return binaryNode;

        // 3. 与当前节点进行比较
        ++BinaryTreeDemo.num;
        if (this.noNumber == no){
            return this;
        }
        return binaryNode;
    }

    /**
     * 删除节点
     *
     */
    public void delNode(int noNumber){
        if (this.leftNode != null && this.leftNode.noNumber == noNumber){
             this.leftNode = null;
             return;
        }
        if (this.rightNode != null && this.rightNode.noNumber == noNumber){
            this.rightNode = null;
            return;
        }
        // 以上不满足，递归左右删除节点
        if (this.leftNode != null)this.leftNode.delNode(noNumber);
        if (this.rightNode != null)this.rightNode.delNode(noNumber);
    }

}